package my.union;

import java.util.Arrays;

/**
 * 最优 Union Find 策略
 * 1.Quick Union
 * 2.基于 rank 的优化(使树变平)
 * 3.Path Halving(路径减半)
 *
 * @author AJun
 * @date 2020/11/1
 */
public class OptimalUnionFind extends AbstractUnionFind {

    private final int[] ranks;

    public OptimalUnionFind(int capacity) {
        super(capacity);

        ranks = new int[capacity];
        // 初始化都是 1
        Arrays.fill(ranks, 1);
    }

    /**
     * 路径分裂
     */
    @Override
    public int find(int v) {
        rangeCheck(v);
        while (v != parents[v]) {
            parents[v] = parents[parents[v]]; // 指向祖父节点
            v = parents[v];
        }
        return v;
    }

    /**
     * 基于 rank 的优化
     */
    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) {
            return;
        }

        if (ranks[p1] < ranks[p2]) {
            parents[p1] = p2;
        } else if (ranks[p1] > ranks[p2]) {
            parents[p2] = p1;
        } else {
            parents[p1] = p2;
            // 如果高度相等则将 p1 嫁接到 p2 上，并将 p1 的高度 +1
            ranks[p2] += 1;
        }
    }

}
